The network alignment problem in graph matching is well-known. Each input network can be represented as a graph G=(V, E) where V is a set of nodes and E is a set of edges. Further, G may be a weighted graph, i.e., a confidence measure w(e) may be associated with each edge e in E. The graphs may have arbitrary structure. The goal in network alignment is to identify one or more possible mappings between the nodes of the input networks and, for each mapping, the corresponding set of conserved edges. Mappings may be partial, i.e., they need not be defined for all the nodes in the networks. Each mapping implies a common subgraph between the two networks; when node a1 from network G1 is mapped to node a2 from network G2, then a1 and a2 refer to the same node in the common subgraph; the edges in the common subgraph correspond to the conserved edges.
A classic problem of graph isomorphism is determining whether one graph can be exactly mapped onto a second. Another known problem is determining a maximum common subgraph, where the goal is to discover the largest graph that is isomorphic to some subgraph in both the networks. Both these problems typically look only at undirected, unweighted, and unannotated graphs. A related but different graph matching problem arises where graphs have edge weights and hence an exact match may not be desired. The matching problem is also complicated when graphs include node feature scores that are used to find a mapping between the nodes, as those scores may not correspond to a maximum common subgraph yet still are appropriate for the given domain.